package Sep.Post;

import java.util.ArrayList;
import java.util.List;

public class Post {
    
}


class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {         this.val = val;
         this.left = left;
         this.right = right;
      }
}
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode p = root;
        TreeNode tmp = null;
        while(p!=null){
            if(p.left==null) p = p.right;
            else{
                tmp = p.left;
                while(tmp.right!=null&&tmp.right!=p) tmp = tmp.right;
                if(tmp.right==null){
                    tmp.right = p;
                    p = p.left;
                }else{
                    tmp.right = null;
                    addPath(ans, p.left);
                    p = p.right;
                }
            }
        }
        addPath(ans, root);
        return ans;
    }

    private void addPath(List<Integer> l,TreeNode r){
        List<Integer> tmp = new ArrayList<>();
        while(r!=null){
            tmp.add(r.val);
            r= r.right;
        }
        for(int i= tmp.size()-1;i>=0;i--){
            l.add(tmp.get(i));
        }
    }
}
